home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / route.arc / BOARD.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-11-24  |  6.8 KB  |  253 lines
  1. #include <stdio.h>
  2.  
  3. #ifndef M_XENIX
  4. #include <stdlib.h>
  5. #endif
  6.  
  7. #include "cell.h"
  8.  
  9. #define LIMIT    0x10000        /* 64k */
  10.  
  11. /* board dimensions */
  12. int Nrows = ILLEGAL;
  13. int Ncols = ILLEGAL;
  14.  
  15. int InitBoardDone = 0; /* sanity check */
  16.  
  17. /* memory usage */
  18. long Ltotal = 0; /* for board */
  19. long Itotal = 0; /* for dist */
  20. long Ctotal = 0; /* for dir */
  21.  
  22. /*
  23. ** memory is allocated in blocks of rows. as many rows as will fit in 64k are
  24. ** allocated in each block. blocks are linked together by pointers. the last
  25. ** block has a null 'next' pointer. if you want to route some *really* big
  26. ** boards (so big that 640k is not sufficient), you should change the
  27. ** algorithms below to test for Lotus-Intel-Microsoft expanded memory (LIM 3.2
  28. ** or 4.0) and use it if present. this would be a major enhancement, so if you
  29. ** do it i hope you will send it back to me so that it can be incorporated in
  30. ** future versions.
  31. */
  32.  
  33. struct lmem { /* a block of longs */
  34.     struct lmem far *next;     /* ptr to next block */
  35.     long         mem[1]; /* more than 1 is actually allocated */
  36.     };
  37.  
  38. struct imem { /* a block of ints */
  39.     struct imem far *next;     /* ptr to next block */
  40.     int         mem[1]; /* more than 1 is actually allocated */
  41.     };
  42.  
  43. struct cmem { /* a block of chars */
  44.     struct cmem far *next;     /* ptr to next block */
  45.     char         mem[1]; /* more than 1 is actually allocated */
  46.     };
  47.  
  48. struct lhead { /* header of blocks of longs */
  49.     int         numrows; /* number of rows per block */
  50.     struct lmem far *side[2]; /* ptr to first block of each chain */
  51.     };
  52.  
  53. struct ihead { /* header of blocks of ints */
  54.     int         numrows; /* number of rows per block */
  55.     struct imem far *side[2]; /* ptr to first block of each chain */
  56.     };
  57.  
  58. struct chead { /* header of blocks of chars */
  59.     int         numrows; /* number of rows per block */
  60.     struct cmem far *side[2]; /* ptr to first block of each chain */
  61.     };
  62.  
  63. static struct lhead Board = { 0, {NULL,NULL} }; /* 2-sided board */
  64. static struct ihead Dist = { 0, {NULL,NULL} }; /* path distance to cells */
  65. static struct chead Dir = { 0, {NULL,NULL} }; /* pointers back to source */
  66.  
  67. extern int justboard;
  68.  
  69. extern char far *Alloc( long );
  70.  
  71. void InitBoard( void );
  72. long GetCell( int, int, int );
  73. void SetCell( int, int, int, long );
  74. void OrCell( int, int, int, long );
  75. int GetDist( int, int, int );
  76. void SetDist( int, int, int, int );
  77. int GetDir( int, int, int );
  78. void SetDir( int, int, int, int );
  79.  
  80. void InitBoard () { /* initialize the data structures */
  81.     long lx, ly; /* for calculating block sizes */
  82.     struct lmem far * far *ltop;     /* for building board chain */
  83.     struct lmem far * far *lbottom;     /* for building board chain */
  84.     struct imem far * far *itop;     /* for building dist chain */
  85.     struct imem far * far *ibottom;     /* for building dist chain */
  86.     struct cmem far * far *ctop;     /* for building dir chain */
  87.     struct cmem far * far *cbottom;     /* for building dir chain */
  88.     int r, c, i, j, k; /* for calculating number of rows per block */
  89.  
  90.     InitBoardDone = 1; /* we have been called */
  91. /* allocate Board (longs) */
  92.     for (lx = (long)Ncols*sizeof(long), ly = 0, i = 0;
  93.         i < Nrows && ly <= LIMIT - sizeof(long far *); ly += lx, i++)
  94.         ; /* calculate maximum number of rows per block */
  95.     Board.numrows = --i;
  96.     ltop = &(Board.side[TOP]);
  97.     lbottom = &(Board.side[BOTTOM]);
  98.     for (j = Nrows; j > 0; j -= i) {
  99.         k = (j > i) ? i : j;
  100.         ly = ((long)k * lx) + sizeof(long far *);
  101.         *ltop = (struct lmem far *)Alloc( ly );
  102.         *lbottom = (struct lmem far *)Alloc( ly );
  103.         Ltotal += 2*ly;
  104.         ltop = (struct lmem far * far *)(*ltop);
  105.         lbottom = (struct lmem far * far *)(*lbottom);
  106.         }
  107.     *ltop = *lbottom = NULL;
  108.     if (!justboard) {
  109. /* allocate Dist (ints) */
  110.         for (lx = (long)Ncols*sizeof(int), ly = 0, i = 0;
  111.             i < Nrows && ly <= LIMIT - sizeof(int far *);
  112.             ly += lx, i++)
  113.             ; /* calculate maximum number of rows per block */
  114.         Dist.numrows = --i;
  115.         itop = &(Dist.side[TOP]);
  116.         ibottom = &(Dist.side[BOTTOM]);
  117.         for (j = Nrows; j > 0; j -= i) {
  118.             k = (j > i) ? i : j;
  119.             ly = ((long)k * lx) + sizeof(int far *);
  120.             *itop = (struct imem far *)Alloc( ly );
  121.             *ibottom = (struct imem far *)Alloc( ly );
  122.             Itotal += 2*ly;
  123.             itop = (struct imem far * far *)(*itop);
  124.             ibottom = (struct imem far * far *)(*ibottom);
  125.             }
  126.         *itop = *ibottom = NULL;
  127. /* allocate Dir (chars) */
  128.         for (lx = (long)Ncols*sizeof(char), ly = 0, i = 0;
  129.             i < Nrows && ly <= LIMIT - sizeof(char far *);
  130.             ly += lx, i++)
  131.             ; /* calculate maximum number of rows per block */
  132.         Dir.numrows = --i;
  133.         ctop = &(Dir.side[TOP]);
  134.         cbottom = &(Dir.side[BOTTOM]);
  135.         for (j = Nrows; j > 0; j -= i) {
  136.             k = (j > i) ? i : j;
  137.             ly = ((long)k * lx) + sizeof(char far *);
  138.             *ctop = (struct cmem far *)Alloc( ly );
  139.             *cbottom = (struct cmem far *)Alloc( ly );
  140.             Ctotal += 2*ly;
  141.             ctop = (struct cmem far * far *)(*ctop);
  142.             cbottom = (struct cmem far * far *)(*cbottom);
  143.             }
  144.         *ctop = *cbottom = NULL;
  145.         }
  146. /* initialize everything to empty */
  147.     for (r = 0; r < Nrows; r++) {
  148.         for (c = 0; c < Ncols; c++) {
  149.             SetCell( r, c, TOP, (long)EMPTY );
  150.             SetCell( r, c, BOTTOM, (long)EMPTY );
  151.             if (!justboard) {
  152.                 SetDist( r, c, TOP, EMPTY );
  153.                 SetDist( r, c, BOTTOM, EMPTY );
  154.                 SetDir( r, c, TOP, EMPTY );
  155.                 SetDir( r, c, BOTTOM, EMPTY );
  156.                 }
  157.             }
  158.         }
  159.     }
  160.  
  161. long GetCell( r, c, s ) /* fetch board cell */
  162.     int r, c, s;
  163.     {
  164.     struct lmem far *p;
  165.  
  166.     p = Board.side[s];
  167.     while (r >= Board.numrows) {
  168.         p = p->next;
  169.         r -= Board.numrows;
  170.         }
  171.     return( p->mem[r*Ncols+c] );
  172.     }
  173.  
  174. void SetCell( r, c, s, x ) /* store board cell */
  175.     int r, c, s;
  176.     long x;
  177.     {
  178.     struct lmem far *p;
  179.  
  180.     p = Board.side[s];
  181.     while (r >= Board.numrows) {
  182.         p = p->next;
  183.         r -= Board.numrows;
  184.         }
  185.     p->mem[r*Ncols+c] = x;
  186.     }
  187.  
  188. void OrCell( r, c, s, x ) /* augment board cell */
  189.     int r, c, s;
  190.     long x;
  191.     {
  192.     struct lmem far *p;
  193.  
  194.     p = Board.side[s];
  195.     while (r >= Board.numrows) {
  196.         p = p->next;
  197.         r -= Board.numrows;
  198.         }
  199.     p->mem[r*Ncols+c] |= x;
  200.     }
  201.  
  202. int GetDist( r, c, s ) /* fetch distance cell */
  203.     int r, c, s;
  204.     {
  205.     struct imem far *p;
  206.  
  207.     p = Dist.side[s];
  208.     while (r >= Dist.numrows) {
  209.         p = p->next;
  210.         r -= Dist.numrows;
  211.         }
  212.     return( p->mem[r*Ncols+c] );
  213.     }
  214.  
  215. void SetDist( r, c, s, x ) /* store distance cell */
  216.     int r, c, s, x;
  217.     {
  218.     struct imem far *p;
  219.  
  220.     p = Dist.side[s];
  221.     while (r >= Dist.numrows) {
  222.         p = p->next;
  223.         r -= Dist.numrows;
  224.         }
  225.     p->mem[r*Ncols+c] = x;
  226.     }
  227.  
  228. int GetDir( r, c, s ) /* fetch direction cell */
  229.     int r, c, s;
  230.     {
  231.     struct cmem far *p;
  232.  
  233.     p = Dir.side[s];
  234.     while (r >= Dir.numrows) {
  235.         p = p->next;
  236.         r -= Dir.numrows;
  237.         }
  238.     return( (int)(p->mem[r*Ncols+c]) );
  239.     }
  240.  
  241. void SetDir( r, c, s, x ) /* store direction cell */
  242.     int r, c, s, x;
  243.     {
  244.     struct cmem far *p;
  245.  
  246.     p = Dir.side[s];
  247.     while (r >= Dir.numrows) {
  248.         p = p->next;
  249.         r -= Dir.numrows;
  250.         }
  251.     p->mem[r*Ncols+c] = (char)x;
  252.     }
  253.